package 图论;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author TTDB
 * @create 2025/9/18
 */
public class canFinish {
    //DFS
     public boolean canFinish(int numCourses, int[][] prerequisites){
         //创建邻接表
         List<List<Integer>> adjacency = new ArrayList<>();
         for (int i = 0; i < numCourses; i++)
             adjacency.add(new ArrayList<>());
         int[] flags = new int[numCourses];
         for (int[] cp : prerequisites)
             adjacency.get(cp[1]).add(cp[0]);
         for (int i = 0; i < numCourses; i++)
             if (!dfs(adjacency, flags, i)) return false;
         return true;
     }
     public boolean dfs(List<List<Integer>> adjacency, int[] flags, int i){
         if(flags[i] == 1) return false;
         if(flags[i] == -1) return true;
         flags[i] = 1;
         for(Integer j : adjacency.get(i))
             if(!dfs(adjacency, flags, j)) return false;
         flags[i] = -1;
         return true;
     }
     //BFS
        public boolean canFinish2(int numCourses, int[][] prerequisites) {
            int[] indegrees = new int[numCourses];
            List<List<Integer>> adjacency = new ArrayList<>();
            Queue<Integer> queue = new LinkedList<>();
            for(int i = 0; i < numCourses; i++)
                adjacency.add(new ArrayList<>());
            // Get the indegree and adjacency of every course.
            for(int[] cp : prerequisites) {
                indegrees[cp[0]]++;
                adjacency.get(cp[1]).add(cp[0]);
            }
            // Get all the courses with the indegree of 0.
            for(int i = 0; i < numCourses; i++)
                if(indegrees[i] == 0) queue.offer(i);
            // BFS TopSort.
            while(!queue.isEmpty()) {
                int pre = queue.poll();
                numCourses--;
                for(int cur : adjacency.get(pre))
                    if(--indegrees[cur] == 0) queue.offer(cur);
            }
            return numCourses == 0;
        }

}
